package com.ctwom.algorithm.questions.Hfind;

/**
 * 用二分查找查询无重复元素的无序数组中某一个局部最小值返回
 * 局部最小值定义：
 * 1、如果第0个元素小于第1个元素，由于第0个元素左边没有元素，所以第0个元素是局部最小值
 * 2、如果第N个元素小于第N-1个元素，由于第N个元素右边没有元素，所以第N个元素是局部最小值
 * 3、如果第i个元素小于第i-1个元素同时也小于第i+1个元素，那么第i个元素就是局部最小值
 */
public class LocalMinimumFind {
    public static void main(String[] args) {
        int[] arr = {5,3,7,4,8,88,2,0,345,1,5};
        System.out.println(localMinimumFind(arr));
    }
    public static int localMinimumFind(int[] arr){
        if(arr[0] < arr[1]){
            return arr[0];
        }
        if(arr[arr.length-1] < arr[arr.length-2]){
            return arr[arr.length-1];
        }
        int start = 0;
        int end = arr.length;
        int n = arr.length;
        while(n >= 1){
            n = (end - start) / 2;
            if(arr[start + n] < arr[start+n+1]){
                end = start + n;
            }else {
                start = start + n;
            }
        }
        return arr[end];
    }
}
